package Hot_100;

import java.util.Scanner;

//爬楼梯
public class Hot_100_70 {
    /**
     * 主函数
     *
     * @param args
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        //调用处理函数并输出结果
        System.out.println(climbStairs(n));
    }

    /**
     * 求数量函数
     *
     * @param n
     * @return
     */
//    public static int climbStairs(int n) {
//        int[] dp = new int[n + 1];
//        //base case
//        dp[0] = 1;
//        dp[1] = 1;
//        //动态规划
//        for(int i = 2; i <= n; i++) {
//            //转移方程
//            dp[i] = dp[i - 1] + dp[i - 2];
//        }
//        return dp[n];
//    }
    public static int climbStairs(int n) {
        //状态压缩
        int a = 1, b = 1, sum = 1;
        for (int i = 1; i < n; i++) {
            a = b;
            b = sum;
            sum = a + b;
        }
        return sum;
    }
}
//时间复杂度: O(n)
//空间复杂度: O(1)
